package 前缀和;

import java.util.HashMap;
import java.util.Map;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 和为K的子数组.java
 * @Description TODO
 * @createTime 2020年11月15日 14:47:00
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 *
 * 示例 1 :
 *
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
 *
 *
 *
 */
public class 和为K的子数组 {
    class Solution {
        public int subarraySum(int[] nums, int k) {
            int N = nums.length;

            int[] presum = new int[N+1];
            int sum = 0;
            //前缀和是预处理  如果直接暴露 有有三重循环
            for (int i = 0; i < N; i++) {
                presum[i] = sum;
                sum += nums[i];
            }
            presum[N] = sum;

            int count = 0;
            for (int i = 0; i <= N; i++) {
                for (int j = i+1; j <= N; j++) {
                    if (presum[j] - presum[i] == k) {
                        count++;
                    }
                }
            }
            return count;
        }

    }


    //用哈希表进行优化


//    public class Solution {
//
//        public int subarraySum(int[] nums, int k) {
//            // key：前缀和，value：key 对应的前缀和的个数
//            Map<Integer, Integer> preSumFreq = new HashMap<>();
//            // 对于下标为 0 的元素，前缀和为 0，个数为 1
//            preSumFreq.put(0, 1);
//
//            int preSum = 0;
//            int count = 0;
//            for (int num : nums) {
//                preSum += num;
//
//                // 先获得前缀和为 preSum - k 的个数，加到计数变量里
//                if (preSumFreq.containsKey(preSum - k)) {
//                    count += preSumFreq.get(preSum - k);
//                }
//
//                // 然后维护 preSumFreq 的定义
//                preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
//            }
//            return count;
//        }
//    }

}
